package gu.struct;

import gu.common.Arrays;

public class BinaryHeap {

	public int[] heap;
	public int count = 0;
	boolean max;
	
	boolean swap;
	
	int idx;
	int parentIdx;
	int parentVal;
	int val;	
	
	int child2Idx;
	int child1Idx;	
	int child2Val;
	int child1Val;	
	int bestChildIdx;
	int bestChildVal;
	
	public BinaryHeap(int size, boolean max) {
		heap = new int[size];
		this.max = max;
	}
	
	public BinaryHeap(int size) {
		this(size, false);
	}
	
	
	public final void add(int val) {
		heap[count++] = val;
		balanceAdd();
	}
	
	public final int pop() {
		int tmp = getFirst();
		balancePop();
		return tmp;
	}
	
	/**
	 * Replace item in heap. Important: works only if newVal is better than oldValue (according to max attribute)
	 * @param oldVal
	 * @param newVal
	 */
	public final void replaceWithBetter(int oldVal, int newVal) {
		boolean found = false;
		for(idx=0;idx<count;idx++) {
			if(oldVal == heap[idx]) {
				heap[idx] = newVal;
				found = true;
				break;
			}
		}
		if(found)
			balanceAdd(idx);
	}
	
	public final int getFirst() {
		return heap[0];
	}
	
	public final boolean isEmpty() {
		return count == 0;
	}

	private final void balanceAdd() {
		balanceAdd(count - 1);
	}
	
	private final void balanceAdd(int idx) {
		if(count == 1 || idx == 0)
			return;
		
		parentIdx = ((idx + 1) >> 1) - 1;
		parentVal = heap[parentIdx];
		val = heap[idx];

		swap = max ? parentVal < val : parentVal > val;
		
		while(swap) {
			heap[parentIdx] = val;
			heap[idx] = parentVal;

			idx = parentIdx;
			parentIdx = ((idx + 1) >> 1) - 1;
			
			if(parentIdx < 0)
				return;
			
			parentVal = heap[parentIdx];
			val = heap[idx];
			swap = max ? parentVal < val : parentVal > val;
		}
	}
	
	private final void balancePop() {
	
		if(count == 0)
			return;
		
		idx = count - 1;
		val = heap[--count];
		bestChildIdx = 0;
		bestChildVal = 0;
		
		boolean swap = false;
		
		do { 
			heap[bestChildIdx] = val;
			heap[idx] = bestChildVal;

			//System.out.print("step: ");
			//print();
			
			idx = bestChildIdx;
			val = heap[idx];
			
			child2Idx = (idx + 1) << 1;
			child1Idx = child2Idx - 1;

			if(child2Idx >= count) {
				if(child1Idx >= count)
					return;
				else {
					child1Val = heap[child1Idx];
					bestChildIdx = child1Idx;
					bestChildVal = heap[bestChildIdx];
					swap = max ? bestChildVal > val : bestChildVal < val;
				}
			} else {
				child1Val = heap[child1Idx];
				child2Val = heap[child2Idx];
				
				if(max)
					bestChildIdx = child1Val > child2Val ? child1Idx : child2Idx;
				else
					bestChildIdx = child1Val < child2Val ? child1Idx : child2Idx;
				
				bestChildVal = heap[bestChildIdx];
				
				swap = max ? bestChildVal > val : bestChildVal < val;
			}

			
		} while(swap);
		
	}	
	
	
	public void print() {
		System.out.println("heap(" + count + ") = " + Arrays.toString(heap));
	}
	
}
